package leetcode.year2021.month11;

// 718. 最长重复子数组
public class _12_2FindLength718 {
  public int findLength(int[] nums1, int[] nums2) {
    // 使用动态规划，dp[i][j] 表示以 nums1下标i为结尾的 与 nums2下标j为结尾的 最长相等子串数量
    // 初始化dp[0][*] 与 dp[*][0]
    int n1 = nums1.length;
    int n2 = nums2.length;
    int ans = 0;
    int[][] dps = new int[n1][n2];
    for (int i = 0; i < n1; i++) {
      dps[i][0] = nums1[i] == nums2[0] ? 1 : 0;
      ans = Math.max(dps[i][0],ans);
    }
    for (int i = 0; i< n2; i++) {
      dps[0][i] = nums1[0] == nums2[i] ? 1 : 0;
      ans = Math.max(dps[0][i],ans);
    }

    for (int i = 1; i < n1; i++) {
      for (int j = 1; j< n2; j++){
        dps[i][j] = nums1[i] == nums2[j] ? dps[i-1][j-1] + 1 : 0;
        ans = Math.max(dps[i][j],ans);
      }
    }
    return ans;
  }
//  public int findLength(int[] nums1, int[] nums2) {
//    int maxLength = 0;
//    int n1 = nums1.length;
//    int n2 = nums2.length;
//    return n1 <= n2 ? getMaxSameLength(nums1,nums2) : getMaxSameLength(nums2,nums1);
//  }
//
//  // 获取当前相交区域的最大相同数量
//  private int getMaxSameLength(int[] nums1, int[] nums2) {
//    int max = 0;
//    int m = nums1.length, n = nums2.length;
//
//    // nums1,nums2中较短的数组不动，这里默认nums1，较长的数组滑动
//    //        初始位置：nums2右边界挨着nums1左边界，nums2从左往右滑动
//    for (int len = 1; len <= m; len++){
//      max = Math.max(max,maxLen(nums1,0,nums2,n-len,len));
//    }
//
//    // 第一阶段：nums2从左往右滑动，两数组重合部分长度不断增加，重合部分长度len从1开始增加
//    //        // 重合部分：nums1起点下标0，nums2起点下标n-len，
//    for (int j = n - m; j>= 0; j--){
//      max = Math.max(max,maxLen(nums1,0,nums2,j,m));
//    }
//
//    //         // 第二阶段：nums2从左往右滑动，两数组重合部分长度不变，重合部分长度始终为nums1长度m
//    //        //  重合部分：nums1起点下标0，nums2起点下标n-m，然后递减
//    for (int i = 1; i < m; i++){
//      max = Math.max(max,maxLen(nums1,i,nums2,0,m-i));
//    }
//    return max;
//  }
//
//  //     /**
//  //    nums1中下标i开始，nums2中下标j开始，长度为len子数组中，最长公共子数组(注意要连续)长度
//  //     */
//  private int maxLen(int[] nums1, int i, int[] nums2, int j, int len) {
//    int count = 0, res = 0;
//    for (int k = 0; k < len; k++){
//      if (nums1[i+k] == nums2[j+k]){
//        count++;
//      } else if (count > 0){
//        res = Math.max(count,res);
//        count = 0;
//      }
//    }
//
//    return count > 0 ? Math.max(count,res) : res;
//  }

  /**
   * 718. 最长重复子数组
   * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
   *
   *
   *
   * 示例：
   *
   * 输入：
   * A: [1,2,3,2,1]
   * B: [3,2,1,4,7]
   * 输出：3
   * 解释：
   * 长度最长的公共子数组是 [3, 2, 1] 。
   *
   *
   * 提示：
   *
   * 1 <= len(A), len(B) <= 1000
   * 0 <= A[i], B[i] < 100
   */
}
